package com.cn.codebrush.练习;

/**
 * @Author Boolean
 * @Date 2022/5/29 17:47
 * @Version 1.0
 */
public class No53最大子数组和 {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray3(nums,0,nums.length-1));
    }


    /**
     * 分治法
     * @param nums
     * @return
     */
    public static int maxSubArray3(int[] nums,int left,int right) {
        if(left == right){
            return nums[left];
        }else {
            int mid = (left+right)/2;
            int leftMax = maxSubArray3(nums,left,mid);
            int rightMax = maxSubArray3(nums,mid+1,right);
            int midMax = maxSubArray3Helper(nums,left,right,mid);
            if(leftMax >= rightMax && leftMax >= midMax){
                return leftMax;
            }else if(rightMax >= leftMax && rightMax >= midMax){
                return rightMax;
            }else {
                return midMax;
            }
        }
    }
    public static int maxSubArray3Helper(int[] nums,int left,int right,int mid) {
        int leftVal = Integer.MIN_VALUE;
        int rightVal = Integer.MIN_VALUE;
        int sum = 0;
        for(int i=mid;i>=left;i--){
            sum += nums[i];
            if(sum > leftVal){
                leftVal = sum;
            }
        }
        sum = 0;
        for(int j=mid+1;j<=right;j++){
            sum += nums[j];
            if(sum > rightVal){
                rightVal = sum;
            }
        }

        return leftVal+rightVal;
    }




    /**
     * 动态规划
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int i=1;i<n;i++){
            dp[i] = dp[i-1]<0?nums[i]:dp[i-1]+nums[i];
        }

        int res = dp[0];
        for(int j=0;j<n;j++){
            res = res>dp[j]?res:dp[j];
        }

        return res;
    }


    /**
     * 贪心算法
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        int n = nums.length;
        int sum = nums[0];
        int res = nums[0];
        for(int i=1;i<n;i++){
            sum = Math.max(sum+nums[i],nums[i]);
            res = Math.max(sum,res);
        }

        return res;
    }
}
